/*
 * @lc app=leetcode.cn id=491 lang=cpp
 *
 * [491] 递增子序列
 *
 * https://leetcode-cn.com/problems/increasing-subsequences/description/
 *
 * algorithms
 * Medium (53.01%)
 * Likes:    437
 * Dislikes: 0
 * Total Accepted:    74.8K
 * Total Submissions: 141.2K
 * Testcase Example:  '[4,6,7,7]'
 *
 * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 * 
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [4,6,7,7]
 * 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [4,4,3,2,1]
 * 输出：[[4,4]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 15
 * -100 <= nums[i] <= 100
 * 
 * 
 */

// @lc code=start
class Solution {
// private:
//     vector<int> path;
//     vector<vector<int>> res;
//     void backtracking(vector<int>& nums, int startIndex) {

//         if(path.size() > 1) {
//             res.push_back(path);
//         }

//         unordered_set<int> used;
//         for(int i = startIndex; i < nums.size(); i++) {
//             if(!path.empty() && nums[i] < path.back() || (used.find(nums[i]) != used.end())) 
//                 continue;
//             path.push_back(nums[i]);
//             used.insert(nums[i]);
//             backtracking(nums, i+1);
//             path.pop_back();
//         }
//     }

// 复盘
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int> nums, int startIndex) {
        if(path.size() > 1) {
            res.push_back(path);
        }

        if(startIndex > nums.size()) return;

        unordered_set<int> used;
        for(int i = startIndex; i < nums.size(); i++) {
            // 当path是非空的，并且，如果path的最后一个元素的值 >(大于)将要处理的值，可以直接返回了
            if(!path.empty() && path.back() > nums[i] || used.find(nums[i]) != used.end()) continue;

            // 这个used集合存储的是 这同一树层 的元素
            // 因为不能排序，所以用集合的方式实现哈希表
            // 当同一层有相同的元素使用过之后，就不要再来遍历了一遍了，
            // 也可以使用数组的方式实现，根据题目要求，-100 <= nums[i] <= 100
            used.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums, i+1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        path.clear();
        res.clear();
        backtracking(nums, 0);
        return res;
    }
};
// @lc code=end

